#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int n = 8;
const int MVNum = 8;
typedef string VerTexType;
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;

} ArcNode;
typedef struct VNode
{
    VerTexType data;
    ArcNode *firstarc;


} VNode, AdjList[MVNum];
typedef struct ALGraph
{

    AdjList vertices;
    int vexnum, arcnum;


} ALGraph;

void create(ALGraph &G)
{
    
    for(int i = 0; i < MVNum; i ++){
        
        G.vertices[i] = *(new VNode());
        G.vertices[i].data = "v" + to_string(i+1);
        G.vertices[i].firstarc = NULL;
    }
    
    G.vertices[0].firstarc = new ArcNode();
    G.vertices[0].firstarc->adjvex = 1;
    
    G.vertices[0].firstarc->nextarc = new ArcNode();
    G.vertices[0].firstarc->nextarc->adjvex = 2;
    G.vertices[0].firstarc->nextarc->nextarc = NULL;
    
    ArcNode *pa = new ArcNode();
    pa->adjvex = 0;
    pa->nextarc = NULL;
    G.vertices[1].firstarc = pa;
    
    pa = new ArcNode();
    pa->adjvex = 3;
    pa->nextarc = NULL;
    G.vertices[1].firstarc->nextarc = pa;
    
    pa = new ArcNode();
    pa->adjvex = 4;
    pa->nextarc = NULL;
    G.vertices[1].firstarc->nextarc->nextarc = pa;

    
    G.vertices[2].firstarc = new ArcNode();
    G.vertices[2].firstarc->adjvex = 1;
    
    G.vertices[2].firstarc->nextarc = new ArcNode();
    G.vertices[2].firstarc->nextarc->adjvex = 5;
    
    G.vertices[2].firstarc->nextarc->nextarc = new ArcNode();
    G.vertices[2].firstarc->nextarc->nextarc->adjvex = 6;
    G.vertices[2].firstarc->nextarc->nextarc->nextarc = NULL;
    
    G.vertices[3].firstarc = new ArcNode();
    G.vertices[3].firstarc->adjvex = 1;
    
    G.vertices[3].firstarc->nextarc = new ArcNode();
    G.vertices[3].firstarc->nextarc->adjvex = 7;
    G.vertices[3].firstarc->nextarc->nextarc = NULL;

    
    G.vertices[4].firstarc = new ArcNode();
    G.vertices[4].firstarc->adjvex = 1;
    
    G.vertices[4].firstarc->nextarc = new ArcNode();
    G.vertices[4].firstarc->nextarc->adjvex = 7;
    G.vertices[4].firstarc->nextarc->nextarc = NULL;

    
    G.vertices[5].firstarc = new ArcNode();
    G.vertices[5].firstarc->adjvex = 2;
    
    G.vertices[5].firstarc->nextarc = new ArcNode();
    G.vertices[5].firstarc->nextarc->adjvex = 6;
    G.vertices[5].firstarc->nextarc->nextarc = NULL;


    G.vertices[6].firstarc = new ArcNode();
    G.vertices[6].firstarc->adjvex = 2;
    
    G.vertices[6].firstarc->nextarc = new ArcNode();
    G.vertices[6].firstarc->nextarc->adjvex = 5;
    G.vertices[6].firstarc->nextarc->nextarc = NULL;


    G.vertices[7].firstarc = new ArcNode();
    G.vertices[7].firstarc->adjvex = 3;
    
    G.vertices[7].firstarc->nextarc = new ArcNode();
    G.vertices[7].firstarc->nextarc->adjvex = 4;
    G.vertices[7].firstarc->nextarc->nextarc = NULL;

}

int visited[n]; //初值为FALSE
void DFS(ALGraph &G, int i)
{
    cout << G.vertices[i].data;
    visited[i] = 1;
    ArcNode *p = G.vertices[i].firstarc;
    while (p != NULL)
    {
        int w = p->adjvex;
        if (!visited[w])
            DFS(G, w);
        p = p->nextarc;
    }
}

int main(int argc, char const *argv[])
{
    for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
    }
    ALGraph G;
    create(G);
    DFS(G, 0);
    
    return 0;
}
